//
//  insertion-sort.cpp
//  
//
//  Created by 茂杰 汤 on 12-4-16.
//  Copyright (c) 2012年 清华大学. All rights reserved.
//

#include <iostream>

using namespace std;

const int arraySize = 10;

void insertionSort(int array[]);

int main()
{
	int a[arraySize] = {5, 2, 4, 6, 1, 7, 3, 0, 9, 8};
	insertionSort(a);
	for (int i = 0; i < arraySize; ++i) {
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

// 升序
void insertionSort(int array[])
{
	int key = 0;
	for (int j = 1; j < arraySize; ++j) {
		key = array[j];
		int i = j -1;
		while (i >= 0 && array[i] > key) {
			array[i+1] = array[i];
			i--;
		}
		array[i+1] = key;
	}
}